package com.LeetCode.Math;

import org.junit.Test;

/**
 * 计数质数
 */
public class CountPrimes {

    public int countPrimes(int n) {
        int res = 0, sqrt_n = (int) Math.sqrt(n);
        boolean[] isPrime = new boolean[n];
        if(2 < n) res++;
        for(int i = 3; i<n; i+=2){
            if(!isPrime[i]){
                if(i <= sqrt_n){
                    for(int j = i; j * i < n; j += 2){
                        isPrime[i * j] = true;
                    }
                }
                res++;
                System.out.println(i);
            }
        }
        return res;
    }

    @Test
    public void test(){
        System.out.println(countPrimes(100));
    }
}
